The present invention relates to the field of digital image transport. More specifically, in one embodiment the present invention provides an improved means for converting the pixels of a digital image between a stream of pixels in raster order and a stream of pixels in block order, or vice versa.
The typical digitized image is represented by a set of pixel values, where each pixel value indicates the color of the image at one point in a two-dimensional grid covering the image. If the image is monochromatic, a pixel value indicates the intensity, from light to dark, of the image at the grid point for that pixel. If the image is a color image, a pixel value might comprise one component for luminance (Y), and two components for chrominance (C.sub.r, C.sub.b), or components in other color spaces such as CYMK (cyan-yellow-magenta-black), and RGB (red-green-blue), etc. The image can be viewed by displaying dots whose color or intensity depend on the pixel values on a physical display device (such as a television or printer) in positions corresponding to the grid points for those pixel values. If the pixels are presented by an image source to the display device in a particular order, the image source and the display device must agree on the pixel order. For example, a non-interlaced computer monitor accepts the pixels of the image to be displayed on the monitor in a specific order, namely raster order.
Raster order begins with the upper-left pixel of the image, followed by the pixels of the upper line of the image, from left to right, followed by the pixels of the second line of the image, from left to right, and so on, down to the right-most pixel of the bottom line of the image. Typically, the pixels of one image are immediately followed by the pixels of a following image. A standard for a stream of multiple images is described in "Coding of Moving Pictures and Associated Audio--for Digital Storage Media", by the MPEG (Moving Pictures Experts Group). One use for a stream of multiple images is to create a moving image such as that displayed on a television monitor.
The pixels of a digital image, instead of being presented by an image source to a raster-order display device, might be presented to digital video processors. In image terminology, an "image source" provides the image and an "image sink" uses the image. One operation performed by a video processor is the compression of an image. One standard for compression, JPEG (Joint Photographic Experts Group), first divides the image into blocks each containing a square of 8.times.8 pixels, and then sequentially compresses one block at a time. As is known in the art of image compression, compressing pixels a block at a time yields good compression ratios for most images. However, the blocking of pixels presents a problem where the images to be compressed are presented by the image source in raster order, as the video processor must store multiple raster lines of pixels until all the pixels of a block are received. Conversely, if an image is presented in block order, as would be expected at the output of a JPEG video decompressor, the pixel stream must be converted from a block order to a raster order if the image sink is a raster-order device. In the 8.times.8 block order, the upper-left pixel of the image is presented first, followed by the next seven pixels of the image's top row, left to right, as in the case of raster order. However, the eighth pixel is followed by the left-most 8 pixels of the second line. This pattern repeats down to the eighth row of the first block, and then the upper-left pixel of the second block (the ninth pixel from the left of the top line of the image) is the 65th pixel to be output in block order. Thus, the pixels of the first block are followed by the pixels of the second block to its right, in turn followed by the pixels in blocks to the right of the second block, until the right edge of the image is reached. This row of blocks defines one image band. The first image band is followed by a second image band, until the entire image is presented. For further background on reordering of pixels, see JPEG, "CD10918-1 Digital Compression and Coding of Continuous-Tone Still Images".
One converter for reordering a raster-ordered image into a block-ordered image reads the raster-ordered image into a two-dimensional array, one band at a time, loading each pixel into a memory location corresponding to that pixel's raster position. Once the entire band is loaded into the array (which has a capacity of at least a full band of pixels), the pixels are then read out of the memory in block order. This converter is not entirely practical where the raster-ordered pixels form a continuous stream and the block-ordered pixels must be output in a continuous stream, since there are large gaps in the output stream while the array is filling and large blockages of the input stream, since no input is accepted while the array is emptying.
A similar converter converts block-ordered images to raster-ordered images.
One solution to the gap problem is to use two band memories and alternate between them to keep up a continuous input and output. While one memory is being filled, the other is being emptied. When the memory being filled is full and the memory being emptied is empty, which should be at the same time, their roles are reversed. This is known as "ping-ponging" memories.
FIG. 1 shows such an reordering converter 10 which uses a two band memories to perform the reordering. Since raster-to-block and block-to-raster conversion are symmetrical, only one case, of a raster-to-block converter, are discussed here in detail.
Converter 10 comprises band memory 0 (16), band memory 1 (18), multiplexer 20, address generators 22, 24, and inverter 26. An input of converter 10 which carries an input stream of pixels in raster order is coupled to the data inputs of both band memories. A line carrying a state signal is coupled to a write enable input of band memory 0, and the line is also coupled to a write enable input of band memory 1, through inverter 26. The outputs of band memories 0, 1 are coupled to inputs of multiplexer 20, which has a select input controlled by the state signal. The address of band memory 0 is provided by address generator 22, while the address of band memory 1 is provided by address generator 24. Address generators 22, 24 are clocked by a pixel clock, which is either a clock generated from the pixel stream or provided by another source which is synchronous with the pixel stream. Address generator 22 generates an address which dictates the location in band memory 0 which is read from and written to; address generator 24 generates the address of locations in band memory 1.
Initially, the state signal is set to a value of 0, indicating that the current state is state 0. In state 0, the state signal enables the writing of the input pixel stream into band memory 1, and multiplexer 20 outputs pixels from band memory 0. Thus, in state 0, band memory 1 fills with pixels, and band memory 0 empties. Once band memory 1 is full and band memory 0 is empty, the state changes to state 1.
In state 1, the reverse is true: the state signal enables the writing of the input pixel stream into band memory 0, and multiplexer 20 outputs pixels from band memory 1, causing band memory 0 to fill with pixels, and band memory 1 to empty. The reordering of pixels occurs when the sequence of addresses output by address generators 22, 24 form one sequence when a memory is being filled, and another sequence when a memory is being emptied.
For a raster-to-block converter, address generator 24 might generate an address sequence in raster order in state 0, and then in state 1, generate an address sequence which would read the pixels out of band memory 24 in block order. Address generator 22 operates similarly, but generates the raster order addresses in state 1, and the block-reordered address sequence in state 0. In this way, a continuous stream of pixels can be accepted into either band memory 0 or 1, and a continuous stream of pixels can be output from the band memory into which data is not being written.
While converter 10 successfully reorders pixels, it does so at a large cost of chip real estate. For example, with 8 pixel by 8 pixel blocks, a image width of 4096 pixels (512 blocks), and 8 bits (1 byte) of data representing each pixel, band memories 0, 1 require 64K (65536) bytes of RAM.
As the above discussion points out, an improved means for converting an image back and forth between block and raster orderings without using large amounts of memory is needed.